#!/usr/bin/env python
# -*- coding: utf-8 -*-
import random
li = [0,1,2,3,4,5,6,7,8,9]
#查找
def linary_search(li,val):
    for i,v in enumerate(li):
        if v == val:
            return i
def binary_search(li,val):
    left = 0
    right = len(li) -1
    while left <= right:
        mid = (left+right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            right = mid -1
        else:
            left = mid + 1

# try:
#     print("线性查找结果：%s,二分查找结果：%s" %(linary_search(li,3),binary_search(li,3)))
# except:
#     print("查找报错")

#冒泡排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def bubble_sort(li):
    for i in range(len(li)-1):
        exchange = True
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1],li[j]
                exchange = False
        print(li)
        if exchange:
            return

#bubble_sort(li)
#查找排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def select_sort_simple(li):
    li_new = []
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new
def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1,len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i],li[min_loc] = li[min_loc],li[i]
        print(li)


#print(select_sort_simple(li))
#select_sort(li)

#插入排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def insert_sort(li):
    for i in range(1,len(li)):
        j = i - 1
        tmp = li[i]
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
        print(li)
#insert_sort(li)

#快速排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def partition_sort(li,left,right):
    tmp = li[left]
    while left < right:
        if left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        if left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left
def quick_sort(li,left,right):
    if left < right:
        mid = partition_sort(li,left,right)
        quick_sort(li,left,mid-1)
        quick_sort(li,mid+1,right)
# quick_sort(li,0,len(li)-1)
# print(li)

#堆排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def sift_sort(li,low,high):
    i = low
    j = 2*i + 1
    tmp = li[i]
    while j <= high:
        if j + 1 <= high and li[j] < li[j+1]:
            j = j + 1
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp

def heap_sort(li):
    n = len(li)
    for i in range(n // 2 -1,-1,-1):
        sift_sort(li,i,n-1)
    for i in range(n-1,-1,-1):
        li[0], li[i] = li[i], li[0]
        sift_sort(li,0,i-1)

# heap_sort(li)
# print(li)
#归并排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def merge(li,low,mid,high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp
def merge_sort(li,low,high):
    if low < high:
        mid = (low+high) // 2
        merge_sort(li,low,mid-1)
        merge_sort(li,mid+1,high)
        merge(li,low,mid,high)

#希尔排序
li = [174, 321, 399, 92, 566, 153, 226, 816, 856, 136]
def insert_sort_gap(li,gap):
    for i in range(gap,len(li)):
        j = i -gap
        tmp = li[i]
        while j>= 0 and tmp < li[j]:
            li[j+gap] = li[j]
            j -= gap
        li[j+gap] = tmp
def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li,d)
        d //= 2
# shell_sort(li)
# print(li)

# try:
#     shell_sort(lii)
#     print("希尔排序结果：%s" %lii)
# except:
#     print("希尔排序报错")

#计数排序
# def count_sort(li,max_count=1000):
#     count = [0 for _ in range(max_count+1)]
#     for val in li:
#         count[val] += 1
#     li.clear()
#     for ind,val in enumerate(count):
#         for i in range(val):
#             li.append(ind)

def count_sort(li,max_count = 100):
    count = [0 for _ in range(max_count+1)]
    for val in li:
        count[val] += 1
    li.clear()
    for ind,val in enumerate(count):
        for i in range(val):
            li.append(ind)

import random

li = [random.randint(0,10) for _ in range(15)]
print(li)
count_sort(li)
print(li)







